#include <iostream>
#include <vector>
#include <stdexcept>
#include "queue.h"
#include "heap_node.h"

queue::queue(): h_size(0), 
				h_array(1, heap_node()), 
				h_dict(1, 0){
}

queue::queue(int n): h_size(0), 
                     h_array(1, heap_node()), 
                     h_dict(1, 0){

	h_array.reserve(n + 1);
	h_dict.reserve(n + 1);
}

inline int queue::h_parent(int index){
	return index / 2;
}

inline int queue::h_left_child(int index){
	return 2 * index;
}

inline int queue::h_right_child(int index){
	return 2 * index + 1;
}

void queue::h_shift_down(int index){
	heap_node to_shift = h_array[index];
	bool shifting = true;
	int l, r;
	int min = index;
	
	do{
		
		l = h_left_child(index);
		r = h_right_child(index);

       	if(l <= h_size && h_array[l] < to_shift) min = l;

        if(r <= h_size && h_array[r] < to_shift && h_array[r] < h_array[l]) min = r;

        if(min != index){
			h_array[index] = h_array[min];
			h_dict[h_array[index].key] = index;
			index = min;
	    }
		else shifting = false;	
	
	}while(shifting);

	h_array[index] = to_shift;
	h_dict[h_array[index].key] = index;

	return;
}

void queue::h_shift_up(int index) {
	heap_node to_shift = h_array[index];
	bool shifting = true;
	int p;

	while(shifting) 
	{
		p = h_parent(index);
		if(1 <= p && to_shift < h_array[p]){
		
	        h_array[index] = h_array[p];
	        h_dict[h_array[index].key] = index;
	        index = p;
    	}
		else shifting = false;
	}
	h_array[index] = to_shift;
	h_dict[h_array[index].key] = index;
	return;
}

int queue::size(){
	return h_size;
}

void queue::insert(int value){
	h_size++;
	h_array.push_back(heap_node(h_size, value));
	h_dict.push_back(h_size);
	h_shift_up(h_size);
}

void queue::decrease_value(int key, int value){

	if(0 < key && h_dict[key] <= h_size && value <= h_array[h_dict[key]].value){
		h_array[h_dict[key]].value = value;
		h_shift_up(h_dict[key]);
	}
	else throw std::invalid_argument("invalid key or value");
}

void queue::extract_min(){
	if(0 < h_size){
		heap_node front = h_array[1];
		h_array[1] = h_array.back();
		h_array.pop_back();
		h_size--;
		h_dict[front.key] = 0;
		if(0 < h_size) h_shift_down(1);
		return;
	}
	else throw std::out_of_range("empty queue");
}

int queue::min_key(){
	return h_array[1].key;
}

int queue::min_value(){
	return h_array[1].value;
}

bool queue::in(int key){
	return h_dict[key] != 0;
}

void queue::print(){
	//std::vector<h_node>::iterator i;

	//for(i = h_array.begin() ; i != h_array.end(); i++)
	//	std::cout << i->value << " ";
	//std::cout << std::endl;

	////for(j = h_dictionary.begin() ; j != h_dictionary.end(); j++)
	////	std::cout << j->first << "->" << j->second << " ";
	//std::cout << std::endl;
}